package Tree;

import java.util.List;

public class TreeDP {
    //二叉树间的最大距离问题
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int data){
            this.value = data;
        }
    }
    public static int maxDistance(Node head){
        return process_Info(head).maxDistance;
    }
    public static class Info{
        public int maxDistance;
        public int height;
        public Info(int dis , int h){
            maxDistance = dis;
            height = h;
        }
    }
    //返回以 X 为头的整颗树的俩个信息.
    public static Info process_Info(Node x){
        if ( x == null)return new Info(0,0);
        Info leftInfo = process_Info(x.left);
        Info rightInfo = process_Info(x.right);
        //将所有可能性得到
        int p1 = leftInfo.maxDistance;
        int p2 =rightInfo.maxDistance;
        int p3 = leftInfo.height+rightInfo.height+1;
        int maxdistance = Math.max(p3,Math.max(p1,p2));
        int height = Math.max(leftInfo.height,rightInfo.height)+1;
        return new Info(maxdistance,height);
    }
    /*__________________________________分割线________________________________________*/
    public static class Employee{
        public int happy;//这名员工的快乐值
        public List<Employee> nexts;//这名员工的直接下级
    }
    public static int maxHappy(Employee boss){
        Info2 headInfo = process2(boss);
        return Math.max(headInfo.buMaxHappy,headInfo.laiMaxHappy);
    }
    public static class Info2{
        public int laiMaxHappy;
        public int buMaxHappy;
        public Info2(int lai ,int bu){
            laiMaxHappy = lai;
            buMaxHappy =bu;
        }
    }
    private static Info2 process2(Employee x){
        if (x.nexts.isEmpty()){
            // x 是基层员工的时候
            return new Info2(x.happy,0);
        }
        int lai = x.happy;//来的时候最大收益
        int bu =0;//不来的时候最大收益
        for (Employee next : x.nexts){
            Info2 nextInfo = process2(next);
            lai += nextInfo.buMaxHappy;
            bu += Math.max(nextInfo.laiMaxHappy,nextInfo.buMaxHappy);
        }
        return new Info2(lai,bu);
    }

}
